package _go

/*39. 组合总和
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。



示例 1：

输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]
示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：

输入: candidates = [2], target = 1
输出: []
示例 4：

输入: candidates = [1], target = 1
输出: [[1]]
示例 5：

输入: candidates = [1], target = 2
输出: [[1,1]]*/

var res [][]int

func combinationSum(candidates []int, target int) [][]int {
	n := len(candidates)
	if n <= 0 {
		return [][]int{}
	}
	res = [][]int{}
	//排序数组

	dfs(candidates, target, 0, []int{})
	return res
}

//candidates 可用数的数组
//target 目标值 逐层递减的
//index 偏移量 这样可以去掉重复结果
//path 已经收集到的结果集
func dfs(candidates []int, target, index int, path []int) {
	//递归的对出条件
	if 0 == target {
		//一定要copy一次才行 因为go的切片底层实现原因 不拷贝出来结果会有变化
		tmp := make([]int, len(path))
		copy(tmp, path)
		res = append(res, tmp)
		return
	}

	for i := index; i < len(candidates); i++ {
		//不符合条件剪枝
		if target-candidates[i] < 0 {
			continue
		}

		//选择
		path = append(path, candidates[i])
		//向下继续
		dfs(candidates, target-candidates[i], i, path)
		//回溯
		path = path[:len(path)-1]
	}
}
